Giga Games 1/Giga Games.iso/net/vir_real/papers/taylor.vsl

Text File | 1993-06-20 | 24.9 KB | 449 lines

91-06/Sarnoff.info
From: [e-mail] (Herbert H Taylor III)
Subject: Virtual Reality, Volume Visualization and Video (LONG)
Date: Wed, 05 Jun 91 11:27:20 EDT




 The recent series of postings on VR/Video following the exchange
between myself and Chris Shaw have been most informative. I would also
like to publicly thank Chris for asking some very tough questions. I
can certainly take a "whipping" without losing my sense of humour -
although I hope we can both avoid the use of the pejorative. It was
unfortunate that the HDTV emphasis of previous posts defocused the
more important topic of VR Architectures. Chris challenged the
applicability of those ideas to VR and while I remain convinced that
they will prove important they seem to represent a small conceptual
detour. Likewise, a strong technical challenge was raised to our
description of several 3D video based scenarios. Much of the technical
criticism which followed was the result of our poor description of our
ideas. Real-time 3D imagery alone will not be sufficient to construct
and manage entirely "simulated" virtual worlds. We will not be able to
look under the Kitchen table for the "Chewing Gum". (Of course if the
CGI modeler doesn't have a "Chewing Gum" model, "it", to borrow a
favorite colloquial expression of Chris', "ain't there either.")
Whether these limitations preclude the use of 3D imagery as a useful
interface component of VR remains a topic of further research...

 In our original speculative post of ca. 3/10/91, (responding to our
moderators request for summaries of current research), we mused about
our desire to explore what VR will be like in ten years. We admitted
that the system we were using (aka the Princeton Engine) was not a
general solution to VR processing. I hope, however, that we use
Supercomputers as vehicles to explore otherwise impossible ideas.
Machines such as the UNC PxPL5, the CM2 or the Princeton Engine are
not "practical" single user architectures - at least not yet - but
surely in not too many years we will have desktop massive parallelism
with the potential for real-time interactive VR applications. This
leads naturally to motivating questions: will the "ultimate" VR system
of the year 2000 be more SGI-MIMD like - with a large number of
powerful processors in the rendering pipeline - or, will it be a
hybrid of SIMD and MIMD, as in the PxPL5?  Perhaps VR specific
architectures will emerge. What impact does our choice of VR world
model have on architecture? Is the evolution of VR only going to be in
the direction of increasingly realistic CGI rendering?  Are worlds
derived from sampled data going to become more viable?

 What are the applications which motivate future VR architectures?
Certainly, the potential for applications in medicine, architecture,
simulated experience, "gaming" and product design will continue to
provide motivation for developing systems with improved visual realism
and more natural interactions. Likewise, scientific data visualization
offers fertile ground for VR research and future application - where
we have this notion of interacting with and literally "experiencing"
our data. There has been significant independent progress in recent
years in each of the fields of interactive data visualization, VR and
specifically, Volume Visualization (VV), however, it will be the
convergence of all three technologies into a single computing and
interaction framework where the true enabling leap of functionality
will occur. Scientists will be able to simulate and visualize complex
phenomena, in some sense, actually "participate" in their experiments.
This kind of interaction will revolutionize scientific research in
much the same way that the computer itself has.

 There are probably those who will question our enthusiasm and observe
that our scientific forebears drew marvelous insight from very simple
physical models of complex structure without the benefit of computers
or graphics. It is said that the structure of benzene came to Kekule
in a dream. Certainly, Watson and Crick were able to visualize amazing
structure without the benefit of complex "tools"... which is exactly
the point. When the visualization systems of the future are as easy to
use as a box of snap together molecular models, as interactive as the
microscope or as "free associative" as a dream - only then will they
realize their full potential. These advances, however, will come at
great computational cost.

 Where are the computational boundaries for VR? To address these
issues we must first establish complexity bounds for VR in terms of
computation (rendering, dynamics, constraints, etc) and I/O. The
processing requirements of VR have been studied in terms of system
dynamics and constraint satisfaction by [Pentland90] giving O(n**3)
"calculations" per vertex for the dynamical system. For a 1000 objects
with a 1000 vertices a 100 TFLOP performance is required to achieve
interactivity (Assuming 100 floating point operations per system
"calculation"). That astounding number is still two orders removed
from the NEXT generation of supercomputers. The authors propose a
reduced complexity model - still with computational complexity in the
10 GFLOP range to satisfy system constraints and 100MFLOP for the
dynamics. A system which implements this approach is described in
[PentE90]. [Witkin90] also discusses the constrained dynamical system
in some detail. Polygon rendering has been discussed in [Ake88] with
floating point requirements in the range of 40MFLOP for 100,000
polygons. Further research needs to be done to reduce world complexity
and to make higher resolution worlds with complex objects more
tractable on near term computers.

 Several posters to this group have suggested that VR input processing
requirements are quite modest - at least in terms of the data glove.
We might ask how does the complexity scale as more and higher
"resolution" input devices are introduced?  Devices such as the Eye
tracker [Levoy90] and 3D head tracker [Wang90] would seem to add
significant complexity to VR processing requirements even with
dedicated interface hardware.  Comparatively less research has been
done on the physical "output" side of VR. [Minsky90] describes a
system using the sense of touch. What other input or output devices
can we look forward to and what are the performance specs?

  Clearly, the exponential growth of the computational and I/O
requirements of VR will motivate both algorithmic and architectural
solutions. A recent estimate by the US Government projects "terraflop"
commercial Supercomputers before the year 2000 [USG91] with the first
demonstration systems emerging from the DARPA High Performance
Computing Systems (HPCS) initiative in 1992-3. Whether the spectacular
performance of these machines can be fully harnessed for VR remains to
be seen. Perhaps what is really needed is a combination of VR specific
architectures with VR specific algorithms - architectures which are on
the HPCS technology learning curve (i.e. that employ MCM packaging,
superdense ULSI, optical inteconnect, etc) COMBINED with algorithms
which can replace O(n**3) with say O(n log n). A number of research
groups have proposed (and in some cases actually built) "application
specific" or "algorithm specific" visualization computers, including
the well known UNC PxPL5 [Fuchs82], the SUNY CUBE [Kaufman88] and the
Stanford SLAM [Dem86] systems. (We are not sure if a full version of
the later machine was ever built.)  In general, these researchers were
motivated by the desire to explore "future" visualization algorithms.

  Our original motivation in developing the Princeton Engine was the
desire to explore "future" video systems. However, we have found that
its applicability is in no way "limited" to video and it can serve as
a useful architecture to study visualization algorithms and future
visualization systmes. We certainly do believe we can accomplish much
of what we described in our previous posts. After all, the system can
turn over 30 (16bit) GIGAOPS, or over 1 GFLOP (for you scientific
types). More important, ALL system I/O is continuous and transparent
to the CPU. A 48bitx28MHZ (=1.4GBPS) digital input bus and a
64bitx28MHZ (= 1.8GBPS) digital output bus can drive any combination
of analog or digital I/O devices. Transparent, continuous gigabit I/O
should be important to the NEXT generation of VR peripherals: Data
Gloves, eye trackers, you invent it. Finally, while there is no
special system requirement that either the I/O or the application be
"video", a typical application will often COMBINE scientific computing
AND real-time data visualization.

 Reat-time Interactive Volume Visualization
 ------------------------------------------
 To calibrate this machine for graphics applications, we are in the
process of implementing a real-time volume rendering system that can
arbitrarily rotate and render 256x256x256 volumes at 30fps. We believe
we can volume render 1Kx1Kx1K at about 8fps using single axis
rotation. This is possible because the Princeton Engine can perform a
"continuous" real-time transpose (512x512x32bitsx30fps) for very
little CPU cost.  The programmer effectively has an array and its
transpose as working data structures. At any line "time" each
processor has a row and colume of the current frame in hand.
Therefore, "scanline" algorithms are relatively straightforward...

 A number of recent papers suggest that Volume Visualization (VV) and
Virtual Reality are closely related, convergent applications. The
"edvol" system combines a VPL Data Glove and 3SPACE Polhemus Tracker
to provide direct interaction with volumetric data [Kaufman90]. The
authors do not characterize the size and complexity of either the VR
or the VV but do describe it as "small scale". It often seems as
though the electronic "media" believe that VV is "already" a standard
component of VR. This obvious misconception has occured because volume
visualization demos are usually presented as real-time interactive
simulations, when the visualization actually took CPU hours to
orchestrate. But the "dream" clearly is real-time interactive volume
rendering and visualization.  One of the best demonstrations I have
seen of the potential for a VV fly through was presented by Mark Levoy
(then of UNC) using volume rendered CT. In [Levoy89] the intended use
of a head mounted display interface to the PxPL5 is described while in
[Levoy90] the use of eye tracking hardware is described - in both
cases specifically for VV.  UNC's Steve Pizer showed a video of 8fps
single axis rotation volume rendering on PxPL5 at the San Diego
Workshop on VV. A head display system has also been developed at UNC
to assist radiologists in treatment planning.  Although these examples
may not in all cases qualify as pure "VR" they certainly speak to the
potential for a real-time interactive VR interface to a volume
visualization environment.

  Volumetric data sets come in two basic forms: "real" sampled data
(as in CT, MRI, Ultrasound, Optical or Xray Microscopy, etc.)  and
computed or "synthetic" data (weather models, CFD, etc.). In the later
case the volume is usually "simulated" while in the former the "raw"
data is sampled and sometimes preprocessed before the volume is
rendered. For example, before an MRI image is produced the "raw"
sampled data must be Fourier Transformed.  With either approach the
resulting data set is a 3D spatial volume. In the case of synthetic
simulated data there is also a "timestep" - the fluid flows, the
turbine spins, etc. With sampled data there is often no clear notion
of time, the data is entirely static; however, the interaction with
the data can be dynamic and even involve the "introduction" of time. A
traveler passing through a sampled and rendered volume certainly
experiences the passage of time, however, the "world" itself remains
static. By analogy one can imagine walking through a museum (static
sampled "objects") verses walking along the bank of a river (dynamic
simulated "objects"). In our conceptual museum, as we begin to
interact with objects we can simplify the system constraint dynamics
as much as desired, literally "determining" the laws of physics. That
Ming Dynasty vase I knocked over? It never touched the ground. If we
are "in" an MRI or CT museum we might wish to change opacity, point of
view or other parameters which effect our visual perception of the
phenomena we are studying. Of course, the same control of time is
possible in the "synthetic" case, however, only at the risk of
undermining the scientific interpretation of the simulation i.e.
correctly visualizing and understanding the physics is often
fundamental to the experiment.

  With the emergence of increasingly real-time instrumention there is
a second form of sampled data to consider: 3D spatial volumes with
time varying data. Imagine a sampled volume of a living organism or
dynamic micro structure which is updated 30 times a second. If we were
"inside" this museum while it was "open" we could watch cells as they
proceed through nuclear envelope breakdown, divide and emerge as two
identical cells. (We are working with this kind of data now.) The
degree to which this form of interaction is a Virtual Reality results
not from our ability to "alter the experiment" on the fly, but from
our ability to control the dynamics of how we "view" the experiment
while it is taking place. We may ultimately be able to turn up the
heat or add some catalyst to a chemical reaction from within the
Virtual experience but that ability neither defines VR nor does the
absense of that ability preclude VR. IMO, it is the VR observers
perceived sense of simulated presence combined with the ability to
control the visual experience which principally defines the
interaction as VR.

 Two related projects provide sources of volumetric data which we are
using at Sarnoff and which we feel have VR "prospects": from an
experimental ultrasound instrument and from a differential inferential
contrast (DIC) micrograph which produces a sequence of image slices
through a cell embryo. The DIC volume can be acquired at or near
real-time with the latest instrumentation - hence, a "video volume"
(sorry Chris, it really can be...) In the case of the ultrasound
instrument the Princeton Engine will also perform the front-end signal
processing required to produce a volume from the sampled data.
Presently, a "raw" 3D ultrasound data set cannot be acquired in
real-time, however, the signal processing to produce a data volume
from an unprocessed data set can potentially be accomplished in
real-time, as can the Volume Rendering process. The KEY POINT is that
we are going to see more and more real-time instrumentation which can
produce true sampled data volumes. As the aquisition time of systems
such as MRI, ultrasound, Electron Microscopy and DIC decrease we will
also see greater coupling between the front-end signal processing, the
data visualization and perhaps even the user interaction. At a recent
workshop at Princeton University, "Seeing Into Materials: Imaging
Complex Structures", both optical and EM microscopy systems capable of
real-time 3D acquisition were described... Actually "4D" is used to
refer to a 3D spatial volume "moving" in time. BTW, these scientists
have a strong intuitive feel for the potential of VR - at least what
they call "VR". That is, the ability to interact with an experiment -
either in situ OR as part of post analysis - as in our museum
examples.

 Is it fair to ask where in the taxonomy of VR systems we should place
these kinds of applications? True, the worlds are derived from various
real world spectra but the interactions are entirely SIMULATED, one
can change viewing parameters, etc. The exact meaning of virtually
touching "objects" or surfaces in such worlds remains unclear... but
really no more so than in a CGI simulated world where everything is
built from models. In either case the eventual consequence of our
fundamental interactions within a world must be determined by a "law
giver". If I put my data gloved hand directly into the burner of a VR
Kitchen stove what happens?

 It should be noted that there are several potential problems with
these methods of data visualization. First, a number of people report
varying degrees of motion sickness when observing through a head
mounted display. That may be acceptable if I am performing a "hammer-
head" maneuver in my Superdecathalon simulator, but probably is not
acceptable if I am inside someones brain. (Informal Poll: How Many of
you have experienced this effect? RSVP and I will tabulate.) A second
potential problem results from "persistance" effects on the human
visual system. We vividly recall in the early days of VLSI CAD
workstations the problem IC draft persons experienced after long hours
staring at color stripes and squares. [Frome83] describes the so
called "McCollough effect", wherein, after looking at color stripes
for only a short time, high contrast B&W stripes suddenly appear to
have color where none is present. To dramatize this effect during her
talk at DAC83, Francine Frome periodically displayed slides with green
and red stripes. About halfway through the talk she displayed a slide
with a striped "BTL" in bright green foreground offset from a bright
red background - before informing the audience that the slide was
totally black and white! It was quite remarkable. These issues and
other "human factor" issues will need to be fully understood before
head mounted displays achieve broad use and certainly before we let
Nintendo sell one to every ten year old...

 More VR/Video
 -------------
  In our original post we also speculated that multiple camaras might
be used to develop a "Video" data glove or "whole body" interface to a
virtual world. In particular, we asked how such an interface would
impact the future design of the data glove.  We received a number of
thoughtful comments following this post. It is important to note that
the VR world itself COULD STILL be CGI - with video only providing a
framework for interaction. With support for up to six camaras one
could surround participants either individually or collectively with
video. (Remember we pay no CPU cost to load frames into memory from
each camara, however, we do pay once we start to do something with the
data.) Participants might wear "chroma keyed" gloves (wireless gloves
of a reserved key color) or even body suites. Chroma keying is a well
known technique for creating simple special effects such as the
"weatherman" overlay [Ennes77] [Watk90]. We would NOT use this merely
for special effects, however, but to provide a means of isolating the
hands so we can build a useful model. On the Engine the ammount of
processing for each chroma key is only about 5-10% of the "real-time
budget" at 30fps. A second chroma key is used for the background. This
is similar to Myron Kruegers Videoplace which uses white backing
screens. It differs in that Videoplace produces only silhouettes of
"Artificial Reality" participants as a group and provides a limited
framework for identifying individual participants.  ( Don't get me
wrong - Videoplace is still a lot of Fun! - I recently spent a day at
the Franklin Institute watching kids play in it and was impressed by
the overall effect produced. )

 The next major technical step is to be able to exploit this interface
in a useful way. In particular we want to study the effect of multiple
"individual" participants. If two video channels are paired to each
participant with a distinct chroma key can we construct a useful model
and use that to interact with and control the dynamics of the
visualization process. Our present plan will focus on the real-time
recognition of simple hand gestures from each "pair of hands".

 The idea of using sign language as some posters have suggested is
very interesting - particularly coupled with a neural net based
recognizer. Recognizing full ASL in "continuous" real-time by any
approach is probably ambitious, however, a useful subset might be
possible. We have used a neural net approach to detect and remove
characteristic AM impulse noise (aka "hair dryer noise") in a TV
receiver [Pearson90].  One network is trained to detect AM impulses on
an image line and a second network is trained to look at the entire
image and determine which of the detected pulses are really "false"
positives. This program runs in continuous real-time on the Princeton
Engine. We also demonstrated real-time BEP training on a simple three
layer MLP (a total of 86 w's and th's). For hand signs, however, a new
network topology would be required - with the input to the network
derived from the subsampled chroma key image segment of the original
image.  However, if my understanding of "conversational" ASL is
correct - and each hand sign is typically an entire word or concept -
then the resulting training set still might be hugh. Also, I believe
that hand motion itself plays a significant role in the interpretation
of signs - not just in the transition from one sign to another - as in
cursive writing. This implies that a robust sign recognition system
would need to compute a motion vector and use that as part of the
training set.  We would appreciate references to current work...
particularly how one detects individual signs when in "continuous"
conversation i.e.  when does one sign end and the next begin?

  Lastly, a second video experiment would involve the use of the
chroma key to present to each of three remote participants a composite
image of their two neighbors, to form a virtual conference. While this
interaction is entirely real-time we recognize that there will be a
significant limit to the quality of interaction between subjects. We
are interested in the degree of "total" immersion each person
experiences.  If we also mix the audio does the participant "feel"
like he or she is having a conversation with three people.
Unfortunately, I would imagine that the head mounted displays would
tend to undermine intimacy - "perhaps" we could image warp new faces
on everybody - just kidding Chris - although now that I think about
it...

 References
 ----------

[Pentland90] "Computational Complexity Verses Virtual Worlds", A
    Pentland, 1990 Symposium on Interactive 3D Graphics. Vol 24,
    No 2, March 1990, ACM SIGGRAPH

 ( Based on the quality of papers in the proceedings, this must have
been a great conference! )

[Witkin90] "Interactive Dynamics", A Witkin, M Gleicher, W Welch,
    1990 Symposium on Interactive 3D Graphics. Vol 24, No 2, March
    1990, ACM SIGGRAPH

[PentE90] "The ThingWorld Modeling System: Virtual Sculpting by Modal
    Forces" A Pentland, I Essa, M Freidmann, B Horowitz.
    1990 Symposium on Interactive 3D Graphics. Vol 24, No 2, March
    1990, ACM SIGGRAPH

[Ack88] "High Performance Polygon Rendering" K Akeley, T Jermoluk,
    Computer Graphics Vol 22, No 4, August 1988. ACM

[Levoy90] "Gaze Directed Volume Visualization", M Levoy, W Whitaker.
    1990 Symposium on Interactive 3D Graphics. Vol 24, No 2, March
    1990, ACM SIGGRAPH

[Wang90] "A Real-time Optical 3D Tracker For Head Mounted Display
    Systems" J Wang, V Chi, H Fuchs. 1990 Symposium on Interactive
    3D Graphics. Vol 24, No 2, March 1990, ACM SIGGRAPH

[Minsky90,vr-66] "Feeling and Seeing: Issues in Force Display" M
    Minsky, O Ming, O Steele, F Brooks, Jr. 1990 Symposium on
    Interactive 3D Graphics. Vol 24, No 2, March 1990, ACM
    SIGGRAPH

[USG91] "Grand Challenges: High Performance Computing and
    Communications" A Report by the Committee on Physical,
    Mathematical and Engineering Sciences; Federal Coordinating
    Council for Science, Engineering, and Technology; Office of
    Science and Technology Policy.

[Fuchs82] "Developing Pixel-Planes, A Smart Memory Based Raster
    Graphics System", H Fuchs, J Poulton, A Paeth, A Bell. 1982
    Conference on Advanced Research in VLSI.

[Kauf88] "Memory and Processing Architecture for 3D Voxel-Based
    Imagery" A Kaufman, R Bakalash, IEEE Computer Graphics and
    Applications, Volume 8. No 11, November 1988, pg 10-23
    reprinted in "Volume Visualization", edited by A Kaufman, IEEE
    Computer Society, 1991.

[Dem86] "Scan Line Access Memories for High Speed Image
    Rasterization", S.G. Demetrescu. Phd Dissertation, Stanford
    University. June 1986.

[Kauf90] "Direct Interaction with a 3D Volumetric Environment", A
    Kaufman, R Yagel, R Bakalash, 1990 Symposium on Interactive 3D
    Graphics. Vol 24, No 2, March 1990, ACM SIGGRAPH

  (We also highly recommend, "Volume Visualization", edited by A
Kaufman, IEEE Computer Society, 1991 which contains a large survey of
relevant publications.)

[Levoy89] "Design for a Real-Time High Quality Volume Rendering
    Workstation" Chapel Hill Workshop on Volume Visualization,
    1989, Department of Computer Science, University of North
    Carolina. C. Upson, Editor.

[Frome83] "Incorporating the Human Factor in Color CAD Systems", F.S.
    Frome, 20th Design Automation Conference, June 1983, IEEE
    Computer Society.

[Ennes77] "Television Broadcasting: Equipement, Systems and Operating
    Fundamentals", H.W Sams, 1979. pg 319-323

[Watk90] "The Art of Digital Video", John Watkinson, Focal Press,
    1990, pg 75-77

[Pearson90] "Artificial Neural Networks as TV Signal Processors"
    Clay D. Spence, John C. Pearson, Ronald Sverdlove SPIE
    Proceedings Vol. 1469: Applications of Artificial Neural
    networks, 1991